474. Ones and Zeroes

Medium

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.

Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.

Note:

The given numbers of 0s and 1s will both not exceed 100
The size of given string array won’t exceed 600.

Example 1:

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4

Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Example 2:

Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2

Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

最近在刷动态规划的题，这篇文章是我写的动态规划一点想法，和大家分享一下

这题思路也是动态规划，不能用贪心，因为如果你第一反应没有想到用DP来做，想得是用贪心算法来做，比如先给字符串数组排个序，让长度小的字符串在前面，然后遍历每个字符串，遇到0或者1就将对应的m和n的值减小，这种方法在有的时候是不对的，比如对于{“11”, “01”, “10”}，m=2，n=2这个例子，我们将遍历完“11”的时候，把1用完了，那么对于后面两个字符串就没法处理了，而其实正确的答案是应该组成后面两个字符串才对。

动态规划：

对于dp矩阵的设计和转移方程的寻找。最开始的想法是使用一维dp遍历所有strs，但是发现完完全全是不够的。而且又犯了存储信息太少的错误，根本没有利用上m，n，所以用m，n设计一个二维矩阵就水到渠成。但是问题又来了，写的时候发现如果i, j都是从小到大进行遍历的，而且我们需要 $dp[i - zeros][j - ones]$的上一轮数据，就会发现所需要的数据会被新覆盖，所以不如让其从大到小遍历，这是一个重要的小技巧。

from collections import Counter
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        if not strs or (not m and not n): return 0
        dp = [[0] * (n + 1) for _ in range(m+1)]
        dp[0][0] = 0
        for i in range(len(strs)):
            c = Counter(strs[i])
            zeros, ones = c['0'], c['1']
            for i in range(m, -1, -1): # 0
                for j in range(n, -1, -1): # 1
                    if (i - zeros) >= 0 and (j - ones) >= 0:
                        dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
        return dp[m][n]

改良版：

因为从大到小遍历，所以i, j只会越来越小，当 (i - zeros) >= 0 and (j - ones) >= 0不满足时，后面也不会满足，不如就不遍历。

from collections import Counter
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        if not strs or (not m and not n): return 0
        dp = [[0] * (n + 1) for _ in range(m+1)]
        dp[0][0] = 0
        for i in range(len(strs)):
            c = Counter(strs[i])
            zeros, ones = c['0'], c['1']
            for i in range(m, zeros-1, -1): # 0
                for j in range(n, ones-1, -1): # 1
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

        return dp[m][n]

Time complexity: $ O(mnl)$ l is the length of strs

Space complexity: $O(mn)$